Conseils pour la récursivité

Lien Moodle : https://moodle.epita.fr/mod/page/view.php?id=104271

Contenu du cours

Dans l'ordre

C'est quoi la question ?

Avant même d'écrire la fonction, apprenez à décrypter l'énoncé et à déterminer :

que doit faire la fonction exactement
quels sont les paramètres
quelle est la nature du résultat

Tout cela vous permettra de déterminer les spécifications* de votre fonction. Rappel : les spécifications donnent le mode d'emploi de votre fonction. On doit savoir :

ce qu'elle calcule / fait
quels sont les paramètres (leur signification, leur type)
les éventuelles conditions d'appels

Le principe

Vous devez ensuite chercher une solution au problème posé, déterminer le principe.

Plusieurs questions à se poser :

J'ai déjà vu quelque chose ressemblant : doit vous permettre de donner la structure de votre fonction.
Quels sont les différents cas.

Écrivez ensuite le principe, tout en faisant la structure globale de votre fonction (fonction à trous !) :

les différents cas à traiter
pour chaque cas, quelle est la réponse à la question.

Après avoir trouvé une solution pour le cas général, vérifiez que les cas particuliers fonctionnent, si ce n'est pas le cas les ajouter.

Cas particuliers : les fonctions "chapeaux" (voir plus bas pour plus de détails) ; elles sont nécessaires lorsque :

il faut vérifier la validité des paramètres, à faire avant d'appeler la fonction récursive
la fonction récursive nécessite des paramètres supplémentaires (qui n'ont rien à voir avec le problème, mais avec la manière de le résoudre)

Récursivité - résumé

La solution consiste à décomposer le problème selon les cas et à trouver l'équivalent de l'"équation de récurrence".

Quelles sont les différentes possibilités ?
Commencer par les différents cas (éventuellement donnés par la structure de données manipulée : sera vu plus tard avec les listes).
Ajouter les cas liés aux autres paramètres (la valeur à chercher par exemple...), à une propriété donnée (pair, impair...)
L'"équation" de récurrence :
Cas de base = cas d'arrêt !
Exprimer le problème en fonction du même problème "plus petit" : par exemple, si on travaille sur un entier $n$ , en fonction de $n-1$ ou $n/2$ ... = cas récursifs !
Vérifier que les appels récursifs tendent bien vers un cas d'arrêt.

De l'utilisation des fonctions "chapeaux"

Dans certains cas, il y a besoin d'"entourer" les fonctions récursives de "fonctions chapeaux". Un résumé ici.

Vérification de la validité de certains paramètres

Soit la fonction suivante, qui calcule $n!$ $n \in \mathbb{N}$ :

      let rec fact n =
        if n < 0 then
            invalid_arg "fact: n is not a natural"
        else
            if n = 0 then
                1
            else
                n * fact (n-1) ;;

Le premier test sur $n$ est nécessaire pour éviter une récursion infinie ! Cela dit, il n'est utile qu'au premier appel. Le faire à chaque fois, comme ci-dessus, multiplie par 2 le nombre de tests à chaque appel (soit $2n$ tests au lieu de $n$ ). Il est donc plus optimal d'effectuer ce test en dehors de la fonction récursive.

     let fact n =
       if n < 0 then
           invalid_arg "fact: n is not a natural"
       else
         let rec fact_rec = function
             0 -> 1
           | n -> n * fact_rec (n-1)
         in
           fact_rec n ;;

Éliminer les cas particuliers

La fonction chapeau nous permet également d'éliminer certains cas que l'on sait calculer sans récursivité.

Voir la fonction ci-dessous qui calcule $x \times y$ avec $x$ et $y$ dans $\mathbb{Z}$ pour les cas $x=0$ et $x=1$ . Remarque : le paramètre x n'est plus nécessaire dans la fonction récursive.

let multiply x y =
  let rec mult_rec = function
      0 -> 0
    | y -> x + mult_rec (x, y-1)
  in
  match x with
    0 -> 0
  | 1 -> y
  | x ->
      if y < 0 then
        -mult_rec (-y)
      else
        mult_rec y ;;

Appel de la fonction récursive avec des paramètre différents

La fonction mult_rec ci-dessus ne fonctionne pas si $y$ est négatif, dans ce cas la fonction chapeau appelle mult_rec avec $-y$ , ce qui permet à multiply de gérer tous les cas sans avoir eu besoin d'écrire deux fonctions récursives selon le signe de $y$ , ou pire tester ce signe à chaque appel.

Ajout de paramètres supplémentaires

Plusieurs types de paramètres peuvent être ajoutés :

Un "accumulateur" qui servira à accumuler les résultats successifs jusqu'au cas d'arrêt (voir la fonction mirror).
Une information que l'on doit emmener en avançant dans la récursion, car dépend de ce qui s'est passée "avant".
Un compteur, ou indice : un entier, généralement à 0 ou 1 au premier appel, qui "avance" au fur et à mesure des appels pour avancer dans une chaîne de caractères par exemple.

La fonction chapeau ne sert alors qu'à appeler la fonction récursive avec la bonne valeur initiale pour ce paramètre supplémentaire. -->